
 <!DOCTYPE HTML>
<html >
<head>
  <meta charset="UTF-8">
  
    <title>jdk源码分析之Collections--二分查找优化 | Typhoon&#39;s code space</title>
    <meta name="viewport" content="width=device-width, initial-scale=1,user-scalable=no">
    
    <meta name="author" content="typhoon">
    

    
    <meta name="description" content="我们基本上都使用过结合工具类Collections，其重要功能和作用是对结合类的一些操作， 比如，查找集合中指定元素，集合排序以及集合类型排序等等。此篇我们将对Collections源 码中的二分查找做详细分析以及提出优化方案。">
<meta name="keywords" content="Collections二分查找优化">
<meta property="og:type" content="article">
<meta property="og:title" content="jdk源码分析之Collections--二分查找优化">
<meta property="og:url" content="http://scorpioaeolus.oschina.io/2018/08/11/Collections工具类二分查找优化/index.html">
<meta property="og:site_name" content="Typhoon&#39;s code space">
<meta property="og:description" content="我们基本上都使用过结合工具类Collections，其重要功能和作用是对结合类的一些操作， 比如，查找集合中指定元素，集合排序以及集合类型排序等等。此篇我们将对Collections源 码中的二分查找做详细分析以及提出优化方案。">
<meta property="og:image" content="http://scorpioaeolus.oschina.io/typhoon/2018/08/11/Collections工具类二分查找优化/c1.png">
<meta property="og:image" content="http://scorpioaeolus.oschina.io/typhoon/2018/08/11/Collections工具类二分查找优化/c2.png">
<meta property="og:image" content="http://scorpioaeolus.oschina.io/typhoon/2018/08/11/Collections工具类二分查找优化/c3.png">
<meta property="og:image" content="http://scorpioaeolus.oschina.io/typhoon/2018/08/11/Collections工具类二分查找优化/c4.png">
<meta property="og:image" content="http://scorpioaeolus.oschina.io/typhoon/2018/08/11/Collections工具类二分查找优化/c5.png">
<meta property="og:image" content="http://scorpioaeolus.oschina.io/typhoon/2018/08/11/Collections工具类二分查找优化/c6.png">
<meta property="og:image" content="http://scorpioaeolus.oschina.io/typhoon/2018/08/11/Collections工具类二分查找优化/c7.png">
<meta property="og:image" content="http://scorpioaeolus.oschina.io/typhoon/2018/08/11/Collections工具类二分查找优化/c8.png">
<meta property="og:updated_time" content="2018-08-18T11:06:23.266Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="jdk源码分析之Collections--二分查找优化">
<meta name="twitter:description" content="我们基本上都使用过结合工具类Collections，其重要功能和作用是对结合类的一些操作， 比如，查找集合中指定元素，集合排序以及集合类型排序等等。此篇我们将对Collections源 码中的二分查找做详细分析以及提出优化方案。">
<meta name="twitter:image" content="http://scorpioaeolus.oschina.io/typhoon/2018/08/11/Collections工具类二分查找优化/c1.png">

    
    <link rel="alternative" href="/atom.xml" title="Typhoon&#39;s code space" type="application/atom+xml">
    
    
    <link rel="icon" href="/typhoon/img/java.png">
    
    
    <link rel="apple-touch-icon" href="/typhoon/img/jacman.jpg">
    <link rel="apple-touch-icon-precomposed" href="/typhoon/img/jacman.jpg">
    
    <link rel="stylesheet" href="/typhoon/css/style.css">
</head>

  <body>
    <header>
      
<div>
		
			<div id="imglogo">
				<a href="/typhoon/"><img src="/typhoon/img/java.png" alt="Typhoon&#39;s code space" title="Typhoon&#39;s code space"/></a>
			</div>
			
			<div id="textlogo">
				<h1 class="site-name"><a href="/typhoon/" title="Typhoon&#39;s code space">Typhoon&#39;s code space</a></h1>
				<h2 class="blog-motto"></h2>
			</div>
			<div class="navbar"><a class="navbutton navmobile" href="#" title="Menu">
			</a></div>
			<nav class="animated">
				<ul>
					<ul>
					 
						<li><a href="/typhoon/">主页</a></li>
					
						<li><a href="/typhoon/archives">归档</a></li>
					
						<li><a href="/typhoon/about">关于</a></li>
					
					<li>
 					
					<form class="search" action="//google.com/search" method="get" accept-charset="utf-8">
						<label>Search</label>
						<input type="search" id="search" name="q" autocomplete="off" maxlength="20" placeholder="Search" />
						<input type="hidden" name="q" value="site:scorpioaeolus.oschina.io">
					</form>
					
					</li>
				</ul>
			</nav>			
</div>
    </header>
    <div id="container">
      <div id="main" class="post" itemscope itemprop="blogPost">
  
	<article itemprop="articleBody"> 
		<header class="article-info clearfix">
  <h1 itemprop="name">
    
      <a href="/typhoon/2018/08/11/Collections工具类二分查找优化/" title="jdk源码分析之Collections--二分查找优化" itemprop="url">jdk源码分析之Collections--二分查找优化</a>
  </h1>
  <p class="article-author">By
       
		<a href="/typhoon/about" title="typhoon" target="_blank" itemprop="author">typhoon</a>
		
  <p class="article-time">
    <time datetime="2018-08-11T02:48:01.000Z" itemprop="datePublished"> Published 2018-08-11</time>
    
  </p>
</header>
	<div class="article-content">
		
		<div id="toc" class="toc-article">
			<strong class="toc-title">Contents</strong>
		
			<ol class="toc"><li class="toc-item toc-level-5"><a class="toc-link" href="#一、Collections二分查找源码及原理分析"><span class="toc-number">1.</span> <span class="toc-text">一、Collections二分查找源码及原理分析</span></a></li><li class="toc-item toc-level-5"><a class="toc-link" href="#二、Collections二分查找优化点分析与实现"><span class="toc-number">2.</span> <span class="toc-text">二、Collections二分查找优化点分析与实现</span></a></li><li class="toc-item toc-level-5"><a class="toc-link" href="#三、测试验证"><span class="toc-number">3.</span> <span class="toc-text">三、测试验证</span></a><ol class="toc-child"><li class="toc-item toc-level-6"><a class="toc-link" href="#总结"><span class="toc-number">3.1.</span> <span class="toc-text">总结</span></a></li></ol></li></ol>
		
		</div>
		
		<pre><code>    我们基本上都使用过结合工具类Collections，其重要功能和作用是对结合类的一些操作，
比如，查找集合中指定元素，集合排序以及集合类型排序等等。此篇我们将对Collections源
码中的二分查找做详细分析以及提出优化方案。
</code></pre><a id="more"></a>
<h5 id="一、Collections二分查找源码及原理分析"><a href="#一、Collections二分查找源码及原理分析" class="headerlink" title="一、Collections二分查找源码及原理分析"></a>一、Collections二分查找源码及原理分析</h5><pre><code>首先，先看一下Collections二分查找的源码：
</code></pre><figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div><div class="line">36</div><div class="line">37</div><div class="line">38</div></pre></td><td class="code"><pre><div class="line"><span class="comment">/**</span></div><div class="line"> * Searches the specified list for the specified object using the binary</div><div class="line"> * search algorithm.  The list must be sorted into ascending order</div><div class="line"> * according to the &#123;<span class="doctag">@linkplain</span> Comparable natural ordering&#125; of its</div><div class="line"> * elements (as by the &#123;<span class="doctag">@link</span> #sort(List)&#125; method) prior to making this</div><div class="line"> * call.  If it is not sorted, the results are undefined.  If the list</div><div class="line"> * contains multiple elements equal to the specified object, there is no</div><div class="line"> * guarantee which one will be found.</div><div class="line"> *</div><div class="line"> * &lt;p&gt;This method runs in log(n) time for a "random access" list (which</div><div class="line"> * provides near-constant-time positional access).  If the specified list</div><div class="line"> * does not implement the &#123;<span class="doctag">@link</span> RandomAccess&#125; interface and is large,</div><div class="line"> * this method will do an iterator-based binary search that performs</div><div class="line"> * O(n) link traversals and O(log n) element comparisons.</div><div class="line"> *</div><div class="line"> * <span class="doctag">@param</span>  &lt;T&gt; the class of the objects in the list</div><div class="line"> * <span class="doctag">@param</span>  list the list to be searched.</div><div class="line"> * <span class="doctag">@param</span>  key the key to be searched for.</div><div class="line"> * <span class="doctag">@return</span> the index of the search key, if it is contained in the list;</div><div class="line"> *         otherwise, &lt;tt&gt;(-(&lt;i&gt;insertion point&lt;/i&gt;) - 1)&lt;/tt&gt;.  The</div><div class="line"> *         &lt;i&gt;insertion point&lt;/i&gt; is defined as the point at which the</div><div class="line"> *         key would be inserted into the list: the index of the first</div><div class="line"> *         element greater than the key, or &lt;tt&gt;list.size()&lt;/tt&gt; if all</div><div class="line"> *         elements in the list are less than the specified key.  Note</div><div class="line"> *         that this guarantees that the return value will be &amp;gt;= 0 if</div><div class="line"> *         and only if the key is found.</div><div class="line"> * <span class="doctag">@throws</span> ClassCastException if the list contains elements that are not</div><div class="line"> *         &lt;i&gt;mutually comparable&lt;/i&gt; (for example, strings and</div><div class="line"> *         integers), or the search key is not mutually comparable</div><div class="line"> *         with the elements of the list.</div><div class="line"> */</div><div class="line"><span class="keyword">public</span> <span class="keyword">static</span> &lt;T&gt;</div><div class="line"><span class="function"><span class="keyword">int</span> <span class="title">binarySearch</span><span class="params">(List&lt;? extends Comparable&lt;? <span class="keyword">super</span> T&gt;&gt; list, T key)</span> </span>&#123;</div><div class="line">    <span class="keyword">if</span> (list <span class="keyword">instanceof</span> RandomAccess || list.size()&lt;BINARYSEARCH_THRESHOLD)</div><div class="line">        <span class="keyword">return</span> Collections.indexedBinarySearch(list, key);</div><div class="line">    <span class="keyword">else</span></div><div class="line">        <span class="keyword">return</span> Collections.iteratorBinarySearch(list, key);</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<pre><code>    方法的作用和用法简单翻译描述一下，该方法有两个入参，list是待查询的列表，key是要查询的元素，方法的
作用是查询出key在list中的位置并返回。方法使用的限定条件是，list必须是按照元素T的排序方法有序的，否则查
询结果不准确，还有一点主要注意的是，如果list中包含多个相同元素，程序将不确定哪个会被找到(而不是我们常
理解的默认第一个被找到)。如果找到就返回元素下表位置，如果没有找到则返回-1。
    该方法根据入参列表的类型和长度分别采用两种不同的实现，如果列表实现了RandomAccess接口(可以简单理解
为ArrayList)或者列表长度小于5000(可以理解为LinkedList类型长度不是很大)，将使用Collections.indexedBinarySearch
方法查找，否则(可以理解为LinkedList实现且长度大于等于5000)使用Collections.iteratorBinarySearch查找。
    首先先看一下indexedBinarySearch实现：
</code></pre><figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div></pre></td><td class="code"><pre><div class="line"><span class="keyword">private</span> <span class="keyword">static</span> &lt;T&gt;</div><div class="line"><span class="function"><span class="keyword">int</span> <span class="title">indexedBinarySearch</span><span class="params">(List&lt;? extends Comparable&lt;? <span class="keyword">super</span> T&gt;&gt; list, T key)</span> </span>&#123;</div><div class="line">    <span class="keyword">int</span> low = <span class="number">0</span>;</div><div class="line">    <span class="keyword">int</span> high = list.size()-<span class="number">1</span>;</div><div class="line"></div><div class="line">    <span class="keyword">while</span> (low &lt;= high) &#123;</div><div class="line">        <span class="keyword">int</span> mid = (low + high) &gt;&gt;&gt; <span class="number">1</span>;</div><div class="line">        Comparable&lt;? <span class="keyword">super</span> T&gt; midVal = list.get(mid);</div><div class="line">        <span class="keyword">int</span> cmp = midVal.compareTo(key);</div><div class="line"></div><div class="line">        <span class="keyword">if</span> (cmp &lt; <span class="number">0</span>)</div><div class="line">            low = mid + <span class="number">1</span>;</div><div class="line">        <span class="keyword">else</span> <span class="keyword">if</span> (cmp &gt; <span class="number">0</span>)</div><div class="line">            high = mid - <span class="number">1</span>;</div><div class="line">        <span class="keyword">else</span></div><div class="line">            <span class="keyword">return</span> mid; <span class="comment">// key found</span></div><div class="line">    &#125;</div><div class="line">    <span class="keyword">return</span> -(low + <span class="number">1</span>);  <span class="comment">// key not found</span></div><div class="line">&#125;</div></pre></td></tr></table></figure>
<pre><code>这是二分查找的java典型实现，我们先用一张图描述其原理
</code></pre><img src="/typhoon/2018/08/11/Collections工具类二分查找优化/c1.png" alt="collections" title="collections">
<pre><code>   其核心点是三个下标的移动，首先找到列表的头部下标，尾部下标以及中间下标，每次拿中间下标元素值与key相比如果
相等直接返回，如果小于中间元素则mid和hign整体向low移动，如果大于中间元素mid和low整体向hign移动，直到找到元素
返回下标或者没有找到返回最近的元素下标加1。
    再看一下iteratorBinarySearch实现：
</code></pre><figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div></pre></td><td class="code"><pre><div class="line"><span class="keyword">private</span> <span class="keyword">static</span> &lt;T&gt;</div><div class="line"><span class="function"><span class="keyword">int</span> <span class="title">iteratorBinarySearch</span><span class="params">(List&lt;? extends Comparable&lt;? <span class="keyword">super</span> T&gt;&gt; list, T key)</span></span></div><div class="line">&#123;</div><div class="line">    <span class="keyword">int</span> low = <span class="number">0</span>;</div><div class="line">    <span class="keyword">int</span> high = list.size()-<span class="number">1</span>;</div><div class="line">    ListIterator&lt;? extends Comparable&lt;? <span class="keyword">super</span> T&gt;&gt; i = list.listIterator();</div><div class="line"></div><div class="line">    <span class="keyword">while</span> (low &lt;= high) &#123;</div><div class="line">        <span class="keyword">int</span> mid = (low + high) &gt;&gt;&gt; <span class="number">1</span>;</div><div class="line">        Comparable&lt;? <span class="keyword">super</span> T&gt; midVal = get(i, mid);</div><div class="line">        <span class="keyword">int</span> cmp = midVal.compareTo(key);</div><div class="line"></div><div class="line">        <span class="keyword">if</span> (cmp &lt; <span class="number">0</span>)</div><div class="line">            low = mid + <span class="number">1</span>;</div><div class="line">        <span class="keyword">else</span> <span class="keyword">if</span> (cmp &gt; <span class="number">0</span>)</div><div class="line">            high = mid - <span class="number">1</span>;</div><div class="line">        <span class="keyword">else</span></div><div class="line">            <span class="keyword">return</span> mid; <span class="comment">// key found</span></div><div class="line">    &#125;</div><div class="line">    <span class="keyword">return</span> -(low + <span class="number">1</span>);  <span class="comment">// key not found</span></div><div class="line">&#125;</div></pre></td></tr></table></figure>
<pre><code>    其实该方法的实现逻辑和indexedBinarySearch类似，不同之处是获取元素的方式，前者获取元素直接调用list.get(mid)，
而入参的类型决定了其不太适合使用这种方式(区别可以参见ArrayList和LinkedList遍历元素性能对比)，而此处调用了一个内
部封装的get(i, mid)方法，看一下实现：
</code></pre><figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div></pre></td><td class="code"><pre><div class="line"><span class="comment">/**</span></div><div class="line"> * Gets the ith element from the given list by repositioning the specified</div><div class="line"> * list listIterator.</div><div class="line"> */</div><div class="line"><span class="keyword">private</span> <span class="keyword">static</span> &lt;T&gt; <span class="function">T <span class="title">get</span><span class="params">(ListIterator&lt;? extends T&gt; i, <span class="keyword">int</span> index)</span> </span>&#123;</div><div class="line">    T obj = <span class="keyword">null</span>;</div><div class="line">    <span class="keyword">int</span> pos = i.nextIndex();</div><div class="line">    <span class="keyword">if</span> (pos &lt;= index) &#123;</div><div class="line">        <span class="keyword">do</span> &#123;</div><div class="line">            obj = i.next();</div><div class="line">        &#125; <span class="keyword">while</span> (pos++ &lt; index);</div><div class="line">    &#125; <span class="keyword">else</span> &#123;</div><div class="line">        <span class="keyword">do</span> &#123;</div><div class="line">            obj = i.previous();</div><div class="line">        &#125; <span class="keyword">while</span> (--pos &gt; index);</div><div class="line">    &#125;</div><div class="line">    <span class="keyword">return</span> obj;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<pre><code>    入参是迭代器和索引位置，既然是使用迭代器访问，那就注定了不能使用类似RandomAccess支持的随机访问的方式，此方
法的原理是，使用迭代器遍历元素，从元素上获取索引值，然后索引值与入参索引位置比较，如果找到就返回元素，否则返回
null(由于入参index是在迭代器索引值范围内，不会返回null)。此处也再次说明了一个问题，ArrayList比LinkedList随机查
询性能好。
</code></pre><h5 id="二、Collections二分查找优化点分析与实现"><a href="#二、Collections二分查找优化点分析与实现" class="headerlink" title="二、Collections二分查找优化点分析与实现"></a>二、Collections二分查找优化点分析与实现</h5><pre><code>    上述分析了Collections中的二分查找原理与实现，我们来举例思考一个问题，如果给定一个列表有从1到10元素，那么如
果查询-1或者11会如何？
     Collections.indexedBinarySearch代码，查询-1步骤如下：
</code></pre><img src="/typhoon/2018/08/11/Collections工具类二分查找优化/c2.png" alt="collections" title="collections">
<pre><code>Collections.indexedBinarySearch中要执行三次while循环才结束调用。同样，我们查询11步骤如下：
</code></pre><img src="/typhoon/2018/08/11/Collections工具类二分查找优化/c3.png" alt="collections" title="collections">
<pre><code>    这次执行四次才结束调用，到这里我们思考一下，既然列表已经是排好序的，那么在查询一个元素的时候，如果目标元素
比列表中最小的值小或者比最大的值大，是不是可以直接宣告不存在，而不是再去列表中使用二分方式再查询一遍，就算二分
查询性能很好，那么查与不查相比，毫无疑问是不查的性能好，就像0和无穷接近0的正数一样道理。
    那么接下来我们对Collections做一下扩展实现，由于Collections构造器是私有，我们无法继承，所以依照Collections
的二分查找方法，拷贝一份在上边改造。
binarySearch：
</code></pre><figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div></pre></td><td class="code"><pre><div class="line"><span class="keyword">public</span> <span class="keyword">static</span> &lt;T&gt;</div><div class="line"><span class="function"><span class="keyword">int</span> <span class="title">binarySearch</span><span class="params">(List&lt;? extends Comparable&lt;? <span class="keyword">super</span> T&gt;&gt; list, T key)</span> </span>&#123;</div><div class="line">    <span class="keyword">if</span> (list <span class="keyword">instanceof</span> RandomAccess || list.size()&lt;BINARYSEARCH_THRESHOLD)</div><div class="line">        <span class="keyword">return</span> CustomCollections.indexedBinarySearch(list, key);</div><div class="line">    <span class="keyword">else</span></div><div class="line">        <span class="keyword">return</span> CustomCollections.iteratorBinarySearch(list, key);</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<pre><code>indexedBinarySearch:
</code></pre><figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div></pre></td><td class="code"><pre><div class="line"><span class="keyword">private</span> <span class="keyword">static</span> &lt;T&gt;</div><div class="line">    <span class="function"><span class="keyword">int</span> <span class="title">indexedBinarySearch</span><span class="params">(List&lt;? extends Comparable&lt;? <span class="keyword">super</span> T&gt;&gt; list, T key)</span></span></div><div class="line">    &#123;</div><div class="line">        <span class="keyword">int</span> low = <span class="number">0</span>;</div><div class="line">        <span class="keyword">int</span> high = list.size()-<span class="number">1</span>;</div><div class="line">        </div><div class="line">        <span class="keyword">if</span>(list.get(low).compareTo(key) &gt; <span class="number">0</span>) &#123;<span class="comment">//key小于最小值</span></div><div class="line">        	<span class="keyword">return</span> -<span class="number">1</span>;</div><div class="line">        &#125;</div><div class="line">        <span class="keyword">if</span>(list.get(high).compareTo(key) &lt; <span class="number">0</span>) &#123;<span class="comment">//或大于最大值</span></div><div class="line">        	<span class="keyword">return</span> -(high + <span class="number">1</span>);</div><div class="line">        &#125;</div><div class="line">        </div><div class="line">        <span class="keyword">while</span> (low &lt;= high) &#123;</div><div class="line">            <span class="keyword">int</span> mid = (low + high) &gt;&gt;&gt; <span class="number">1</span>;</div><div class="line">            Comparable&lt;? <span class="keyword">super</span> T&gt; midVal = list.get(mid);</div><div class="line">            <span class="keyword">int</span> cmp = midVal.compareTo(key);</div><div class="line"></div><div class="line">            <span class="keyword">if</span> (cmp &lt; <span class="number">0</span>)</div><div class="line">                low = mid + <span class="number">1</span>;</div><div class="line">            <span class="keyword">else</span> <span class="keyword">if</span> (cmp &gt; <span class="number">0</span>)</div><div class="line">                high = mid - <span class="number">1</span>;</div><div class="line">            <span class="keyword">else</span></div><div class="line">                <span class="keyword">return</span> mid; <span class="comment">// key found</span></div><div class="line">        &#125;</div><div class="line">        <span class="keyword">return</span> -(low + <span class="number">1</span>);  <span class="comment">// key not found</span></div><div class="line">    &#125;</div></pre></td></tr></table></figure>
<pre><code>iteratorBinarySearch:
</code></pre><figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div></pre></td><td class="code"><pre><div class="line"><span class="keyword">private</span> <span class="keyword">static</span> &lt;T&gt;</div><div class="line">   <span class="function"><span class="keyword">int</span> <span class="title">iteratorBinarySearch</span><span class="params">(List&lt;? extends Comparable&lt;? <span class="keyword">super</span> T&gt;&gt; list, T key)</span></span></div><div class="line">   &#123;</div><div class="line">       <span class="keyword">int</span> low = <span class="number">0</span>;</div><div class="line">       <span class="keyword">int</span> high = list.size()-<span class="number">1</span>;</div><div class="line">       ListIterator&lt;? extends Comparable&lt;? <span class="keyword">super</span> T&gt;&gt; i = list.listIterator();</div><div class="line">       </div><div class="line">       <span class="keyword">if</span>(get(i, low).compareTo(key) &gt; <span class="number">0</span>) &#123;</div><div class="line">       	<span class="keyword">return</span> -<span class="number">1</span>;</div><div class="line">       &#125;</div><div class="line">       <span class="keyword">if</span>(get(i,high).compareTo(key) &lt; <span class="number">0</span>) &#123;</div><div class="line">       	<span class="keyword">return</span> -list.size();</div><div class="line">       &#125;</div><div class="line">       </div><div class="line">       <span class="keyword">while</span> (low &lt;= high) &#123;</div><div class="line">           <span class="keyword">int</span> mid = (low + high) &gt;&gt;&gt; <span class="number">1</span>;</div><div class="line">           Comparable&lt;? <span class="keyword">super</span> T&gt; midVal = get(i, mid);</div><div class="line">           <span class="keyword">int</span> cmp = midVal.compareTo(key);</div><div class="line"></div><div class="line">           <span class="keyword">if</span> (cmp &lt; <span class="number">0</span>)</div><div class="line">               low = mid + <span class="number">1</span>;</div><div class="line">           <span class="keyword">else</span> <span class="keyword">if</span> (cmp &gt; <span class="number">0</span>)</div><div class="line">               high = mid - <span class="number">1</span>;</div><div class="line">           <span class="keyword">else</span></div><div class="line">               <span class="keyword">return</span> mid; <span class="comment">// key found</span></div><div class="line">       &#125;</div><div class="line">       <span class="keyword">return</span> -(low + <span class="number">1</span>);  <span class="comment">// key not found</span></div><div class="line">   &#125;</div></pre></td></tr></table></figure>
<pre><code>对比Collections，二分查找的具体实现加了这样一段代码：
</code></pre><figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div></pre></td><td class="code"><pre><div class="line"><span class="keyword">if</span>(list.get(low).compareTo(key) &gt; <span class="number">0</span>) &#123;<span class="comment">//key小于最小值</span></div><div class="line">	<span class="keyword">return</span> -<span class="number">1</span>;</div><div class="line">&#125;</div><div class="line"><span class="keyword">if</span>(list.get(high).compareTo(key) &lt; <span class="number">0</span>) &#123;<span class="comment">//或大于最大值</span></div><div class="line">	<span class="keyword">return</span> -(high + <span class="number">1</span>);</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<pre><code>    浅显易懂，假如目标元素key比list中最小元素还小直接返回-1，没必要走二分逻辑；假如目标元素key
比list中最大元素还大，直接返回-(hign+1),同样没必要走二分逻辑。
</code></pre><h5 id="三、测试验证"><a href="#三、测试验证" class="headerlink" title="三、测试验证"></a>三、测试验证</h5><pre><code>接下来，我们使用代码验证猜想，测试代码：
</code></pre><img src="/typhoon/2018/08/11/Collections工具类二分查找优化/c4.png" alt="collections" title="collections">
<pre><code>jdk自带Collections二分查找，遍历第一次low=0，mid=4，hign=9：
</code></pre><img src="/typhoon/2018/08/11/Collections工具类二分查找优化/c5.png" alt="collections" title="collections">
<pre><code>遍历第二次low=0，mid=1，hign=3：
</code></pre><img src="/typhoon/2018/08/11/Collections工具类二分查找优化/c6.png" alt="collections" title="collections">
<pre><code>遍历第三次low=0，mid=0，hign=0：
</code></pre><img src="/typhoon/2018/08/11/Collections工具类二分查找优化/c7.png" alt="collections" title="collections">
<pre><code>遍历第四次，不满足low &lt;= high，程序结束。


改造后的CustomCollections二分查找：
</code></pre><img src="/typhoon/2018/08/11/Collections工具类二分查找优化/c8.png" alt="collections" title="collections">
<pre><code>    可以看出，low=0，hign=9，逻辑走进了我们加的一层校验，命中目标元素小于list列表中最小的元素，
这时候直接返回-1，查询结束，不再进入二分查询逻辑。
</code></pre><h6 id="总结"><a href="#总结" class="headerlink" title="总结"></a>总结</h6><pre><code>    经过上述一系列分析与测试，我们证实了Collections二分查询逻辑存在优化点，并且用代码验证了我们
的猜想，在列表很大的场景下，使用本篇优化过的CustomCollections二分查找必定会带来不小的性能提升，
希望给大家在日常开发中带来帮助！
</code></pre>  
	</div>
		<footer class="article-footer clearfix">
<div class="article-catetags">

<div class="article-categories">
  <span></span>
  <a class="article-category-link" href="/typhoon/categories/java性能优化/">java性能优化</a>
</div>


  <div class="article-tags">
  
  <span></span> <a href="/typhoon/tags/Collections二分查找优化/">Collections二分查找优化</a>
  </div>

</div>



	<div class="article-share" id="share">
	
	  <div data-url="http://scorpioaeolus.oschina.io/2018/08/11/Collections工具类二分查找优化/" data-title="jdk源码分析之Collections--二分查找优化 | Typhoon&#39;s code space" data-tsina="null" class="share clearfix">
	  </div>
	
	</div>


</footer>

   	       
	</article>
	
<nav class="article-nav clearfix">
 
 <div class="prev" >
 <a href="/typhoon/2018/08/18/基于多线程实现通用搜索/" title="基于多线程实现通用搜索">
  <strong>上一篇：</strong><br/>
  <span>
  基于多线程实现通用搜索</span>
</a>
</div>


<div class="next">
<a href="/typhoon/2018/08/04/聊一种哑铃式编程方式/"  title="聊一种哑铃式编程方式">
 <strong>下一篇：</strong><br/> 
 <span>聊一种哑铃式编程方式
</span>
</a>
</div>

</nav>

	


</div>  
      <div class="openaside"><a class="navbutton" href="#" title="Show Sidebar"></a></div>

  <div id="toc" class="toc-aside">
  <strong class="toc-title">Contents</strong>
 
 <ol class="toc"><li class="toc-item toc-level-5"><a class="toc-link" href="#一、Collections二分查找源码及原理分析"><span class="toc-number">1.</span> <span class="toc-text">一、Collections二分查找源码及原理分析</span></a></li><li class="toc-item toc-level-5"><a class="toc-link" href="#二、Collections二分查找优化点分析与实现"><span class="toc-number">2.</span> <span class="toc-text">二、Collections二分查找优化点分析与实现</span></a></li><li class="toc-item toc-level-5"><a class="toc-link" href="#三、测试验证"><span class="toc-number">3.</span> <span class="toc-text">三、测试验证</span></a><ol class="toc-child"><li class="toc-item toc-level-6"><a class="toc-link" href="#总结"><span class="toc-number">3.1.</span> <span class="toc-text">总结</span></a></li></ol></li></ol>
 
  </div>

<div id="asidepart">
<div class="closeaside"><a class="closebutton" href="#" title="Hide Sidebar"></a></div>
<aside class="clearfix">

  


  
<div class="categorieslist">
	<p class="asidetitle">Categories</p>
		<ul>
		
		  
			<li><a href="/typhoon/categories/dubbo/" title="dubbo">dubbo<sup>8</sup></a></li>
		  
		
		  
			<li><a href="/typhoon/categories/java性能优化/" title="java性能优化">java性能优化<sup>17</sup></a></li>
		  
		
		  
			<li><a href="/typhoon/categories/java源码分析/" title="java源码分析">java源码分析<sup>1</sup></a></li>
		  
		
		  
			<li><a href="/typhoon/categories/motan/" title="motan">motan<sup>2</sup></a></li>
		  
		
		  
			<li><a href="/typhoon/categories/spring/" title="spring">spring<sup>11</sup></a></li>
		  
		
		  
			<li><a href="/typhoon/categories/springboot/" title="springboot">springboot<sup>28</sup></a></li>
		  
		
		  
			<li><a href="/typhoon/categories/springmvc/" title="springmvc">springmvc<sup>1</sup></a></li>
		  
		
		  
			<li><a href="/typhoon/categories/容器/" title="容器">容器<sup>1</sup></a></li>
		  
		
		  
			<li><a href="/typhoon/categories/工具/" title="工具">工具<sup>7</sup></a></li>
		  
		
		  
			<li><a href="/typhoon/categories/性能优化/" title="性能优化">性能优化<sup>5</sup></a></li>
		  
		
		  
			<li><a href="/typhoon/categories/架构/" title="架构">架构<sup>8</sup></a></li>
		  
		
		  
			<li><a href="/typhoon/categories/案例分析/" title="案例分析">案例分析<sup>13</sup></a></li>
		  
		
		  
			<li><a href="/typhoon/categories/缓存/" title="缓存">缓存<sup>4</sup></a></li>
		  
		
		  
			<li><a href="/typhoon/categories/设计模式/" title="设计模式">设计模式<sup>3</sup></a></li>
		  
		
		  
			<li><a href="/typhoon/categories/面试题/" title="面试题">面试题<sup>1</sup></a></li>
		  
		
		</ul>
</div>


  
<div class="tagslist">
	<p class="asidetitle">Tags</p>
		<ul class="clearfix">
		
			
				<li><a href="/typhoon/tags/springboot/" title="springboot">springboot<sup>28</sup></a></li>
			
		
			
				<li><a href="/typhoon/tags/java性能优化/" title="java性能优化">java性能优化<sup>9</sup></a></li>
			
		
			
				<li><a href="/typhoon/tags/限流/" title="限流">限流<sup>3</sup></a></li>
			
		
			
				<li><a href="/typhoon/tags/Spring5/" title="Spring5">Spring5<sup>3</sup></a></li>
			
		
			
				<li><a href="/typhoon/tags/设计模式/" title="设计模式">设计模式<sup>3</sup></a></li>
			
		
			
				<li><a href="/typhoon/tags/案例分析/" title="案例分析">案例分析<sup>2</sup></a></li>
			
		
			
				<li><a href="/typhoon/tags/性能优化/" title="性能优化">性能优化<sup>2</sup></a></li>
			
		
			
				<li><a href="/typhoon/tags/Spring/" title="Spring">Spring<sup>2</sup></a></li>
			
		
			
				<li><a href="/typhoon/tags/dubbo/" title="dubbo">dubbo<sup>2</sup></a></li>
			
		
			
				<li><a href="/typhoon/tags/分页/" title="分页">分页<sup>2</sup></a></li>
			
		
			
				<li><a href="/typhoon/tags/并发/" title="并发">并发<sup>2</sup></a></li>
			
		
			
				<li><a href="/typhoon/tags/异常拦截/" title="异常拦截">异常拦截<sup>1</sup></a></li>
			
		
			
				<li><a href="/typhoon/tags/dubbo分布式事务/" title="dubbo分布式事务">dubbo分布式事务<sup>1</sup></a></li>
			
		
			
				<li><a href="/typhoon/tags/自带图片/" title="自带图片">自带图片<sup>1</sup></a></li>
			
		
			
				<li><a href="/typhoon/tags/svn导出mvn项目/" title="svn导出mvn项目">svn导出mvn项目<sup>1</sup></a></li>
			
		
			
				<li><a href="/typhoon/tags/dubbo过滤器/" title="dubbo过滤器">dubbo过滤器<sup>1</sup></a></li>
			
		
			
				<li><a href="/typhoon/tags/排序性能对比/" title="排序性能对比">排序性能对比<sup>1</sup></a></li>
			
		
			
				<li><a href="/typhoon/tags/ListenableFuture/" title="ListenableFuture">ListenableFuture<sup>1</sup></a></li>
			
		
			
				<li><a href="/typhoon/tags/PropertyChangeListener/" title="PropertyChangeListener">PropertyChangeListener<sup>1</sup></a></li>
			
		
			
				<li><a href="/typhoon/tags/jdbcTemplate高可用/" title="jdbcTemplate高可用">jdbcTemplate高可用<sup>1</sup></a></li>
			
		
		</ul>
</div>


  <div class="linkslist">
  <p class="asidetitle">Links</p>
    <ul>
        
          <li>
            
            	<a href="https://coderq.com" target="_blank" title="一个面向程序员交流分享的新一代社区">码农圈</a>
            
          </li>
        
          <li>
            
            	<a href="http://wuchong.me" target="_blank" title="Jark&#39;s Blog">Jark&#39;s Blog</a>
            
          </li>
        
    </ul>
</div>

  


  <div class="rsspart">
	<a href="/atom.xml" target="_blank" title="rss">RSS</a>
</div>

  <div class="weiboshow">
  <p class="asidetitle">Weibo</p>
    <iframe width="100%" height="119" class="share_self"  frameborder="0" scrolling="no" src="http://widget.weibo.com/weiboshow/index.php?language=&width=0&height=119&fansRow=2&ptype=1&speed=0&skin=9&isTitle=1&noborder=1&isWeibo=0&isFans=0&uid=null&verifier=b3593ceb&dpc=1"></iframe>
</div>


</aside>
</div>
    </div>
    <footer><div id="footer" >
	
	<div class="line">
		<span></span>
		<div class="author"></div>
	</div>
	
	
	<section class="info">
		<p> Hello ,I&#39;m a java coder. <br/>
			This is my blog,believe it or not.</p>
	</section>
	 
	<div class="social-font" class="clearfix">
		
		
		
		
		
		
		
		
		
		
		<a href="mailto:ScorpioAeolus@163.com" target="_blank" class="icon-email" title="Email Me"></a>
		
	</div>
			
		

		<p class="copyright">
		Powered by <a href="http://hexo.io" target="_blank" title="hexo">hexo</a> and Theme by <a href="https://github.com/wuchong/jacman" target="_blank" title="Jacman">Jacman</a> © 2019 
		
		<a href="/typhoon/about" target="_blank" title="typhoon">typhoon</a>
		
		
		</p>
</div>
</footer>
    <script src="/typhoon/js/jquery-2.0.3.min.js"></script>
<script src="/typhoon/js/jquery.imagesloaded.min.js"></script>
<script src="/typhoon/js/gallery.js"></script>
<script src="/typhoon/js/jquery.qrcode-0.12.0.min.js"></script>

<script type="text/javascript">
$(document).ready(function(){ 
  $('.navbar').click(function(){
    $('header nav').toggleClass('shownav');
  });
  var myWidth = 0;
  function getSize(){
    if( typeof( window.innerWidth ) == 'number' ) {
      myWidth = window.innerWidth;
    } else if( document.documentElement && document.documentElement.clientWidth) {
      myWidth = document.documentElement.clientWidth;
    };
  };
  var m = $('#main'),
      a = $('#asidepart'),
      c = $('.closeaside'),
      o = $('.openaside');
  c.click(function(){
    a.addClass('fadeOut').css('display', 'none');
    o.css('display', 'block').addClass('fadeIn');
    m.addClass('moveMain');
  });
  o.click(function(){
    o.css('display', 'none').removeClass('beforeFadeIn');
    a.css('display', 'block').removeClass('fadeOut').addClass('fadeIn');      
    m.removeClass('moveMain');
  });
  $(window).scroll(function(){
    o.css("top",Math.max(80,260-$(this).scrollTop()));
  });
  
  $(window).resize(function(){
    getSize(); 
    if (myWidth >= 1024) {
      $('header nav').removeClass('shownav');
    }else{
      m.removeClass('moveMain');
      a.css('display', 'block').removeClass('fadeOut');
      o.css('display', 'none');
      
      $('#toc.toc-aside').css('display', 'none');
        
    }
  });
});
</script>

<script type="text/javascript">
$(document).ready(function(){ 
  var ai = $('.article-content>iframe'),
      ae = $('.article-content>embed'),
      t  = $('#toc'),
      ta = $('#toc.toc-aside'),
      o  = $('.openaside'),
      c  = $('.closeaside');
  if(ai.length>0){
    ai.wrap('<div class="video-container" />');
  };
  if(ae.length>0){
   ae.wrap('<div class="video-container" />');
  };
  c.click(function(){
    ta.css('display', 'block').addClass('fadeIn');
  });
  o.click(function(){
    ta.css('display', 'none');
  });
  $(window).scroll(function(){
    ta.css("top",Math.max(140,320-$(this).scrollTop()));
  });
});
</script>


<script type="text/javascript">
$(document).ready(function(){ 
  var $this = $('.share'),
      url = $this.attr('data-url'),
      encodedUrl = encodeURIComponent(url),
      title = $this.attr('data-title'),
      tsina = $this.attr('data-tsina'),
      description = $this.attr('description');
  var html = [
  '<div class="hoverqrcode clearfix"></div>',
  '<a class="overlay" id="qrcode"></a>',
  '<a href="https://www.facebook.com/sharer.php?u=' + encodedUrl + '" class="article-share-facebook" target="_blank" title="Facebook"></a>',
  '<a href="https://twitter.com/intent/tweet?url=' + encodedUrl + '" class="article-share-twitter" target="_blank" title="Twitter"></a>',
  '<a href="#qrcode" class="article-share-qrcode" title="微信"></a>',
  '<a href="http://widget.renren.com/dialog/share?resourceUrl=' + encodedUrl + '&srcUrl=' + encodedUrl + '&title=' + title +'" class="article-share-renren" target="_blank" title="人人"></a>',
  '<a href="http://service.weibo.com/share/share.php?title='+title+'&url='+encodedUrl +'&ralateUid='+ tsina +'&searchPic=true&style=number' +'" class="article-share-weibo" target="_blank" title="微博"></a>',
  '<span title="Share to"></span>'
  ].join('');
  $this.append(html);

  $('.hoverqrcode').hide();

  var myWidth = 0;
  function updatehoverqrcode(){
    if( typeof( window.innerWidth ) == 'number' ) {
      myWidth = window.innerWidth;
    } else if( document.documentElement && document.documentElement.clientWidth) {
      myWidth = document.documentElement.clientWidth;
    };
    var qrsize = myWidth > 1024 ? 200:100;
    var options = {render: 'image', size: qrsize, fill: '#2ca6cb', text: url, radius: 0.5, quiet: 1};
    var p = $('.article-share-qrcode').position();
    $('.hoverqrcode').empty().css('width', qrsize).css('height', qrsize)
                          .css('left', p.left-qrsize/2+20).css('top', p.top-qrsize-10)
                          .qrcode(options);
  };
  $(window).resize(function(){
    $('.hoverqrcode').hide();
  });
  $('.article-share-qrcode').click(function(){
    updatehoverqrcode();
    $('.hoverqrcode').toggle();
  });
  $('.article-share-qrcode').hover(function(){}, function(){
      $('.hoverqrcode').hide();
  });
});   
</script>









<link rel="stylesheet" href="/typhoon/fancybox/jquery.fancybox.css" media="screen" type="text/css">
<script src="/typhoon/fancybox/jquery.fancybox.pack.js"></script>
<script type="text/javascript">
$(document).ready(function(){ 
  $('.article-content').each(function(i){
    $(this).find('img').each(function(){
      if ($(this).parent().hasClass('fancybox')) return;
      var alt = this.alt;
      if (alt) $(this).after('<span class="caption">' + alt + '</span>');
      $(this).wrap('<a href="' + this.src + '" title="' + alt + '" class="fancybox"></a>');
    });
    $(this).find('.fancybox').each(function(){
      $(this).attr('rel', 'article' + i);
    });
  });
  if($.fancybox){
    $('.fancybox').fancybox();
  }
}); 
</script>



<!-- Analytics Begin -->



<script>
var _hmt = _hmt || [];
(function() {
  var hm = document.createElement("script");
  hm.src = "//hm.baidu.com/hm.js?e6d1f421bbc9962127a50488f9ed37d1";
  var s = document.getElementsByTagName("script")[0]; 
  s.parentNode.insertBefore(hm, s);
})();
</script>



<!-- Analytics End -->

<!-- Totop Begin -->

	<div id="totop">
	<a title="Back to Top"><img src="/typhoon/img/scrollup.png"/></a>
	</div>
	<script src="/typhoon/js/totop.js"></script>

<!-- Totop End -->

<!-- MathJax Begin -->
<!-- mathjax config similar to math.stackexchange -->


<!-- MathJax End -->

<!-- Tiny_search Begin -->

<!-- Tiny_search End -->

  </body>
</html>
